1987. Следующая перестановка

На вход программы поступает строка из десятичных цифр. Вывести перестановку этих десятичных цифр, дающую следующее по величине за заданным десятичное число. Например:

123 → 132

279134399742 → 279134423799

Вполне возможно, что входные данные могут содержать набор цифр, не имеющих искомой следующей перестановки. Например, 987.

Вход. Первая строка содержит количество тестов p (1 ≤ p ≤ 1000). Каждая следующая строка представляет собой отдельный тест и содержит его номер и соответствующий набор из не более чем 80 десятичных цифр.

Выход. Ответ на каждый тест следует выводить в отдельной строке. Если для заданного набора цифр не существует следующей перестановки, то выведите сначала номер теста и далее через пробел строку BIGGEST. Если же решение существует, то сначала выведите также номер теста, а затем через пробел найденную следующую перестановку входных цифр.

Пример входа	Пример выхода
3 1 123 2 279134399742 3 987	1 132 2 279134423799 3 BIGGEST

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Задачу можно решить при помощи функции next_permutation.

Однако далее опишем алгоритм нахождения лексикографически следующей перестановки. Большей будем называть перестановку, в которой раньше встретился элемент, больший соответствующего ему элемента во второй перестановке. Например, если S = (3, 5, 4, 6, 7), а L = (3, 5, 6, 4, 7), то S < L.

Покажем на примере, как найти перестановку, следующую за P = (5, 6, 7, 4, 3). Просматриваем текущую перестановку справа налево, следя за тем, чтобы каждое следующее число было больше предыдущего. Останавливаемся, когда правило нарушится. Место остановки подчеркнуто: (5, 6, 7, 4, 3). Потом снова просматриваем пройденный путь (справа налево) до тех пор, пока не дойдем до первого числа, которое больше отмеченного. Место второй остановки отметим двойным подчеркиванием: (5, 6, 7, 4, 3). Поменяем местами отмеченные числа: (5, 7, 6, 4, 3). Теперь все числа, расположенные справа от двойного подчеркивания, упорядочим в порядке возрастания. Поскольку они до этих пор были упорядочены в убывающем порядке, то достаточно перевернуть указанный отрезок. Получим Q = (5, 7, 3, 4, 6). Это и есть перестановка, непосредственно следующая за P.

Пример. Найдем перестановку, следующую за P = (7, 5, 3, 6, 4, 2, 1).

Реализация алгоритма – STL, next_permutation

Решение при помощи функции next_permutation:

char s[1001];

scanf("%d",&tests);

while(tests--)

{

scanf("%d %s",&cs,s);

len = strlen(s);

flag = next_permutation(s,s+len);

printf("%d ",cs);

if (!flag) puts("BIGGEST"); else puts(s);

}

Реализация алгоритма – генерация перестановки без STL

Входную перестановку храним в массиве s.

char s[1001];

Функция NextPerm генерирует лексикографически следующую перестановку.

int NextPerm(char *s)

{

int Ipos, Jpos;

Ipos = len - 2; Jpos = len - 1;

Ipos указывает на место первой остановки: s[Ipos] подчеркнуто один раз.

while((s[Ipos] >= s[Ipos+1]) && (Ipos >= 0)) Ipos--;

if (Ipos < 0) return 0;

Jpos указывает на место второй остановки: s[Jpos] подчеркнуто два раза.

while(s[Jpos] <= s[Ipos]) Jpos--;

Меняем местами значения s[Ipos] и s[Jpos].

swap(s[Ipos],s[Jpos]);

Переворачиваем хвост перестановки, находящийся правее от двойного подчеркивания.

Jpos = len - 1;

for(Ipos++; Ipos < Jpos; Ipos++, Jpos--) swap(s[Ipos],s[Jpos]);

return 1;

}

Основная часть программы.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %s",&cs,s); len = strlen(s);

printf("%d ",cs);

if (NextPerm(s)) puts(s); else puts("BIGGEST");

}